Gapless power method convergence

If Power method is initialized with a random Gaussian vector then, with high probability, after $T = O(\frac{\log d/\epsilon}{\epsilon})$ steps, we obtain a $\mathbf{z}$ satisfying $$\Vert 𝐗-{𝐗𝐳𝐳}^{𝖳}{\Vert }_F^2\le (1+ϵ)\Vert 𝐗-{𝐗𝐯}_1{𝐯}_1^{𝖳}{\Vert }_F^2$$

Intuition: For a good low-rank approximation, we don’t actually need to converge to v1 if σ1 and σ2 are the same or very close. Would suffice to return either v1 or v2, or some linear combination of the two.

Compare: Basic power method convergence